//集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有
//一个数字重复 。 
//
// 给定一个数组 nums 代表了集合 S 发生错误后的结果。 
//
// 请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,2,4]
//输出：[2,3]
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,1]
//输出：[1,2]
// 
//
// 
//
// 提示： 
//
// 
// 2 <= nums.length <= 104 
// 1 <= nums[i] <= 104 
// 
// Related Topics 位运算 数组 哈希表 排序 
// 👍 233 👎 0

package com.cute.leetcode.editor.cn;

import java.util.HashSet;
import java.util.Set;

public class SetMismatch {
    public static void main(String[] args) {
        Solution solution = new SetMismatch().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /**
     * 我一开始想的太简单了，这个数组的数为1到n，多余的数很容易找到，就是不容易找到缺哪个
     * 气死我了，乍一看觉得很简单，到最后还是把hasp匹配搬出来了
     * 思路：遍历nums，如果set中包含了当前num，说明num重复了 将num添加到结果中去，否则添加num到set
     * 遍历set，因为set是排序的，所以遍历时到第i个set值!=i的时候就说明原数组缺少i这个元素，添加到结果集，返回
     * 如果遍历完了都没事，那说明缺少最大值，n添加到结果集，返回
     * 也可以使用一个数组代替hash表，cnts[num]++进行计数，最后cnts中下标为0代表没出现，下标为2代表重复了
     *
     *
     */
    public int[] findErrorNums(int[] nums) {
        int[] res = new int[2];
        //题解的方法，使用一个数组进行统计
        int[] cnts = new int[nums.length+1];
        for (int num : nums) cnts[num]++;
        for (int i = 1; i <=nums.length ; i++) {
            if (cnts[i] == 0) res[1] = i;
            else if (cnts[i] == 2) res[0] = i;
        }

        /*Set<Integer> set = new HashSet<>();
        for (int num : nums){
            if (set.contains(num)){
                res[0] = num;
                continue;
            }
            set.add(num);
        }
        int i=1;
        for (int num : set){
            if (num!=i){
                res[1] = i;
                return res;
            }
            i++;
        }
        res[1] = nums.length;*/
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}